/**
 * 
 * @author Leah Criscolo
 * 
 * AVL Tree class builds AVL BSTs.
 *
 * @param <K> Generic Key type
 * @param <V> Generic V type
 */
public class AVL<K extends Comparable<K>,V> extends RegBST<K,V> {
	
	/**
	 * Default constructor that sets the root to null
	 * 
	 */
	public AVL()
	{
		root = null;
	}
	
	/**
	 * Constructor for AVL
	 * 
	 * @param key Key value associated with that node
	 * @param value Value associated with that node
	 */
	public AVL(K key, V value)
	{
		root = new BSTNode<K,V>(key,value);
	}
	
	@Override
	/**
	 * Recursively inserts a new node into the AVL tree.
	 * 
	 */
	public void insert(K key, V value)
	{
		root = insert(root, key, value);
	}
	
	/**
	 * Helper function for insertion
	 * 
	 * @param t Recursive parameter
	 * @param key Key of new element
	 * @param value Value of new element
	 * @return new root of the subtree
	 */
	private BSTNode<K,V> insert(BSTNode<K,V> t, K key, V value)
	{		
		if (t == null) {
			t = new BSTNode<K, V>(key, value);
		}
		
		// if the new key is less that t's key, insert it recursively
		else if (t.getKey().compareTo(key) > 0) {
			t.setLeft(insert(t.getLeft(), key, value));
			
			// checking the balance and rotating 
			calcHeightAndBF(root);
            t = avlRotate(t);
			
		} else if (t.getKey().compareTo(key) < 0) {
			t.setRight(insert(t.getRight(), key, value));
			
			calcHeightAndBF(root);
            t = avlRotate(t);
		}

		return t;
	}
	
	@Override
	/**
	 * Remove an element from the tree
	 * 
	 * @param key Key of element to remove
	 */
	public void remove(K key)
	{
		root = remove(root, key);
	}
	
	/**
	 * Helper function for removal.
	 * 
	 * @param t Recursive parameter
	 * @param key Key of element to remove
	 * @return new root of subtree
	 */
	private BSTNode<K,V> remove(BSTNode<K,V> t, K key)
	{
		if (t != null) 
		{
			if (t.getKey().compareTo(key) > 0) 
			{
				t.setLeft(remove(t.getLeft(), key));
				calcHeightAndBF(root);
				t = avlRotate(t);
			} 
			else if (t.getKey().compareTo(key) < 0) 
			{
				t.setRight(remove(t.getRight(), key));
				calcHeightAndBF(root);
				t = avlRotate(t);
			} 
			else 
			{
				if (t.getLeft() == null) 
				{
					t = t.getRight();
				} 
				else if (t.getRight() == null) 
				{
					t = t.getLeft();
				} 
				else 
				{
					// Two children - here's where it get's interesting
					BSTNode<K, V> suc = getSucc(t);
					t.setKey(suc.getKey());
					t.setValue(suc.getValue());
					t.setRight(remove(t.getRight(), t.getKey()));
				}
				
				// check balance
				calcHeightAndBF(root);
				
			}
		}
		return t;
	}
	
	/**
	 * Calculates the balance factor and height for every node beneath t
	 * 
	 * @param t The starting node
	 */
	public void calcHeightAndBF(BSTNode<K,V> t)
	{
		//if it's null
		if(t == null)
		{
			return;
		}
		// if it's a leaf
		if(t.getRight() == null && t.getLeft()==null)
		{
			t.setBf(0);
			t.setHeight(0);
		}
		
		int rightLength = 0;
		int leftLength = 0;
		
		// if no right child, only left child
		if(t.getRight() == null && t.getLeft() != null)
		{
			rightLength = -1;
			calcHeightAndBF(t.getLeft());
			leftLength = t.getLeft().getHeight();
			t.setBf(leftLength-rightLength);
			t.setHeight(leftLength+1);
		}
		// if no left child
		if(t.getRight() != null && t.getLeft() == null)
		{
			leftLength = -1;
			calcHeightAndBF(t.getRight());
			rightLength = t.getRight().getHeight();
			t.setBf(leftLength-rightLength);
			t.setHeight(rightLength + 1);
		}
		// if children on both sides
		if(t.getRight() != null && t.getLeft()!= null)
		{
			calcHeightAndBF(t.getRight());
			calcHeightAndBF(t.getLeft());
			t.setHeight(Math.max(t.getLeft().getHeight(), t.getRight().getHeight())+1);
			t.setBf((t.getLeft().getHeight())-(t.getRight().getHeight()));
		}
		
		
	}
	
	/**
	 * Determines both whether or not a rotation is needed and which rotation to perform.
	 * 
	 * @param t The node being examined 
	 * @return The new root of the subtree
	 */
	public BSTNode<K,V> avlRotate(BSTNode<K,V> t)
	{
		calcHeightAndBF(root);
		if(t == null)
			return t;
		
		if (t.getBf() <= -2)
		{
			if (t.getRight().getBf() < 0)
			{
				t = right(t);
			}
			else if (t.getRight().getBf() > 0)
			{
				t = leftright(t);
			}
		}
		else if (t.getBf() >= 2)
		{
			if (t.getLeft().getBf() > 0)
			{
				t = left(t);
			}
			else if (t.getLeft().getBf() < 0)
			{
				t = rightleft(t);
			}
		}
		
		return t;
	}
	
	/**
	 * Performs a single left rotation.
	 * 
	 * @param t The starting subroot
	 * @return New root of the sub tree
	 */
	public BSTNode<K,V> left(BSTNode<K,V> t)
	{
		if(t == null)
			return t;
		BSTNode<K,V> temp = t.getLeft();
        t.setLeft(temp.getRight());
        temp.setRight(t);
        calcHeightAndBF(root);
        return temp;
	}
	
	/**
	 * Performs a single right rotation.
	 * 
	 * @param t The starting subroot
	 * @return New root of the sub tree
	 */
	public BSTNode<K,V> right(BSTNode<K,V> t)
	{
		if(t == null)
			return t;
		 BSTNode<K,V> temp = t.getRight();
         t.setRight(temp.getLeft());
         temp.setLeft(t);
         calcHeightAndBF(root);
         return temp;
	}
	
	/**
	 * Performs a double left rotation.
	 * 
	 * @param t The starting subroot
	 * @return New root of the sub tree
	 */
	public BSTNode<K,V> leftright(BSTNode<K,V> t)
	{
		if(t == null)
			return t;
		t.setRight(left( t.getRight() ));
        return right( t );
	}
	
	/**
	 * Performs a double right rotation.
	 * 
	 * @param t The starting subroot
	 * @return New root of the sub tree
	 */
	public BSTNode<K,V> rightleft(BSTNode<K,V> t)
	{
		if(t == null)
			return t;
		t.setLeft(right( t.getLeft() ));
        return left( t );
	}

	public void changeStatus(K key)
	{
		changeStatus(root, key);
		
	}

	/**
	 * Helper function for value retrieval
	 * 
	 * @param t
	 *            recursive parameter
	 * @param key
	 *            key to search for
	 * @return value
	 */
	private void changeStatus(BSTNode<K, V> t, K key) {
		if (t == null) {
			return;
		} else if (t.getKey().compareTo(key) > 0) {
			changeStatus(t.getLeft(), key);
		} else if (t.getKey().compareTo(key) < 0) {
			changeStatus(t.getRight(), key);
		}
		else if(t.getKey().compareTo(key) == 0)
		{
			User temp = (User)t.getValue();
			temp.changeStatus();
			return;
		}
	}
	
}
